Merge Sort in C is a sorting algorithm. When you have a large data collection that is not arranged and requires you to search a particular data set in the collection then a sorting technique is used to arrange large data in a sequence. Sorting reduces the time of data searching in large data collection. There are several sorting algorithms are available to apply according to the need of the user.
Merge Sort in C
Here we start with the understanding of basics merge sort in c.
What is Merge Sort?
Like
Quick sort
, Merge sort is also based on the divide and conquer technique. It repeatedly divides a list into sub-lists until each sub-list has only one element and then merges them in a way to get a sorted list at the end. As the list can be divided in the max of logN parts and then merging of all sub-lists into a sorted list takes O(N) time so the worst-case running this algorithm is O(N logN) Let’s understand this with an example to get a better knowledge of merge sort.
This is an example where we have a list of 6 elements. To find the mid element to divide the list- mid= (0+5)/2, n is the position of the last element. Below we can see that in the first step, the list is divided into 2 sub-lists. We have a list containing (9, 7, 8, 3, 2, 1). First divided into 2 lists that are (9, 7, 8) and (3, 2, 1). These lists of size 3 are then divided into again 2 sub-lists of each that is (9, 7) and (8), and (3, 2) and (1). This process will go until we get each sub-lists having single elements. So now we have (9), (7), (8), (3), (2), (1). No further breakdown is possible now. Now 2 sub-lists formed in the last step to be merged in sorted order by comparing them elements. Like 9 and 7 are compared and 7 will be placed before 9. The same applied to others also. And finally, we will get the sorted array as 1, 2, 3, 7, 8, 9.
Example of Merge Sort using C Programming
#include<stdlib.h>
#include<stdio.h>
// Merges two subarrays of arr[].
// 1st subarray is arr[l..m]
// 2nd subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* To create temp arrays */
int L[n1], R[n2];
/* This will copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // starting index of first subarray
j = 0; // starting index of second subarray
k = l; // starting index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there is any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there is any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l meant for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
/* This program to test above functions */
int main()
{
int arr[] = {21, 11, 43, 5, 19, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
Output:
Given array is 21 11 43 5 19 7 Sorted array is 5 7 11 21 19 43
Example of Merge Sort using Java
class MergeSort
{
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
// To check the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// starting indexes of first and second subarrays
int i = 0, j = 0;
// starting index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function for sorting arr[l..r] using
// merge()
void sort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
/* Function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Main method
public static void main(String args[])
{
int arr[] = {21, 11, 43, 5, 19, 7};
System.out.println("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
printArray(arr);
}
}
Output:
Given array is 21 11 43 5 19 7 Sorted array is 5 7 11 21 19 43
Example of Merge Sort using C++
#include <bits/stdc++.h>
using namespace std;
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void applyMergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
applyMergeSort(arr, l, m);
applyMergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main()
{
int arr[] = { 1, 4, 3, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
applyMergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
cout<<arr[i]<<" ";
return 0;
}
Output
1 2 3 4
Example of Merge Sort using Python
def applyMergeSort(arr):
if len(arr) > 1:
mid = len(arr)//2
left = arr[:mid]
right = arr[mid:]
applyMergeSort(left)
applyMergeSort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
if __name__ == '__main__':
arr = [1, 4, 3, 2]
applyMergeSort(arr)
print(arr, end=" ")
Output
[1, 2, 3, 4]
Iterative Merge Sort
Problem
Implement iterative merge sort
Algorithm
Merge sort works by repeatedly merging two sorted arrays and finally obtaining the resultant sorted array. We start from two individual elements and merge them to make a sorted array of two elements. We recursively perform this operation on other subarrays as well. We can perform this algorithm iteratively by using the following approach. The approach takes O(NlogN) time.
Iterative Merge sort in C
#include <stdio.h>
#include <stdlib.h>
int min(int x, int y) {
return (x < y) ? x : y;
}
void merge(int arr[], int temp[], int start, int mid, int end, int n)
{
int k = start, i = start, j = mid + 1;
while (i <= mid && j <= end)
{
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
while (i < n && i <= mid) {
temp[k++] = arr[i++];
}
for (int i = start; i <= end; i++) {
arr[i] = temp[i];
}
}
void mergesort(int arr[], int temp[], int low, int high, int n)
{
for (int m = 1; m <= high - low; m = 2*m)
{
for (int i = low; i < high; i += 2*m)
{
int start = i;
int mid = i + m - 1;
int end = min(i + 2*m - 1, high);
merge(arr, temp, start, mid, end, n);
}
}
}
int main()
{
int arr[] = {1, 4, 3, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int temp[n];
for(int i=0;i<n;i++) temp[i]=arr[i];
mergesort(arr, temp, 0, n - 1, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output
1 2 3 4
Iterative Merge sort in C++
#include<bits/stdc++.h>
using namespace std;
int min(int x, int y) {
return (x < y) ? x : y;
}
void merge(int arr[], int temp[], int start, int mid, int end, int n)
{
int k = start, i = start, j = mid + 1;
while (i <= mid && j <= end)
{
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
while (i < n && i <= mid) {
temp[k++] = arr[i++];
}
for (int i = start; i <= end; i++) {
arr[i] = temp[i];
}
}
void mergesort(int arr[], int temp[], int low, int high, int n)
{
for (int m = 1; m <= high - low; m = 2*m)
{
for (int i = low; i < high; i += 2*m)
{
int start = i;
int mid = i + m - 1;
int end = min(i + 2*m - 1, high);
merge(arr, temp, start, mid, end, n);
}
}
}
int main()
{
int arr[] = {1, 4, 3, 2};
int n = sizeof(arr)/sizeof(arr[0]);
int temp[n];
for(int i=0;i<n;i++) temp[i]=arr[i];
mergesort(arr, temp, 0, n - 1, n);
for (int i = 0; i < n; i++) {
cout<<arr[i]<<" ";
}
return 0;
}
Output
1 2 3 4
Iterative Merge sort in Python
def merge(arr, temp, start, mid, finish): k = start i = start j = mid + 1 while i <= mid and j <= finish: if arr[i] < arr[j]: temp[k] = arr[i] i = i + 1 else: temp[k] = arr[j] j = j + 1 k = k + 1 while i < len(arr) and i <= mid: temp[k] = arr[i] k = k + 1 i = i + 1 for i in range(start, finish + 1): arr[i] = temp[i] def iterativeMergeSort(arr): low = 0 high = len(arr) - 1 temp = arr.copy() m = 1 while m <= high - low: for i in range(low, high, 2*m): start = i mid = i + m - 1 finish = min(i + 2*m - 1, high) merge(arr, temp, start, mid, finish) m = 2*m arr = [1, 2, 4, 3] iterativeMergeSort(arr) print(arr)
Output
[1, 2, 3, 4]
Advantages
- Merge sort can be applied to any size of data collection.
- Time complexity in all cases worst, average and best is O(n log n), which makes it very efficient.
- This is a Stable sorting algorithm.
- During the run-creation step, reading of the input is sequential ==> Not much seeking.
- This is a highly parallelizable algorithm .
- When heap sort is used for the in-memory part of the merge, its operation can be overlapped with I/O.
- Tapes can be used since I/O is largely sequential.
Disadvantages
- This is not an in-place sorting algorithm so extra memory space is required proportional to n.
- This is slower than the Quicksort when sorting large data.
- Merge sort is comparatively less efficient than Quicksort.
Real-Time Application
An e-commerce website “You might like” section is the best example of a merge sort. You all must notice this section whenever you visit the site. They have maintained an array of all user accounts and their choices by the time whenever you visit the site for any purpose. Then they start recommending what you have bought and what you like. In this sorting, the more the number of inversions, the more dissimilar choices are there and fewer inversions mean more similar choices are there.
People are also reading: